Tidak banyak yang diketahui tentang awal kehidupan Gajah Mada. Sesetengah orang[nyatakan menurut siapa?] menyebutkan pekerjaannya sebagai komander Bhayangkara, pengawal elit untuk raja-raja Majapahit dan keluarga mereka. Apabila Rakrian Kuti, salah seorang pegawai di Majapahit, memberontak terhadap raja Majapahit Jayanegara (memerintah 1309-1328) pada 1321, Gajah Mada dan mahapatih pada masa itu Arya Tadah membantu raja dan keluarganya melarikan diri dari ibu negara Majapahit Trowulan. Kemudian, Gajah Mada membantu raja tersebut untuk pulang ke ibu negara dan menghancurkan pemberontakan itu. Tujuh tahun kemudian, Jayanegara telah diracun mati oleh Rakrian Tanca, salah seorang pembantu Rakrian Kuti.

Dalam satu versi lain, menurut Kakawin Nagarakretagama (sebuah puisi epik bahasa Jawa abad ke-14), dan disokong oleh inskripsi akhir abad ke-13 dan awal abad ke-14, Jayanagara dibunuh oleh Gajah Mada pada 1328. Dikatakan[nyatakan menurut siapa?] Jayanagara melindung lampau dua adik tiri perempuannya, puteri permaisuri termuda Kertarajasa, Dyah Dewi Gayatri. Sungutan oleh kedua-dua puteri muda ini menyebabkan adanya campur tangan oleh Gajah Mada. Penyelesaian mendadaknya adalah untuk mengatur seorang pakar bedah agar membunuh raja sambil berpura-pura melakukan pembedahan.

Jayanegara segera digantikan oleh saudara perempuannya Tribhuwana Wijayatunggadewi (memerintah 1328-1350). Di bawah pemerintahannyalah Gajah Mada dilantik sebagai mahapatih pada 1329, selepas persaraan Arya Tadah.

Selaku Mahapatih (Menteri Besar) di bawah Ratu Thribuwana Tunggadewi, Gajah Mada telah menghapuskan pemberontakan di Sadeng dan Keta pada 1331. Semasa pemerintahan Gajah Mada sebagai Mahapatih juga, seorang pengembara Muslim yang terkenal iaitu Ibn Battuta telah melawat Kepulauan Indonesia sekitar tahun 1345.